{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Fibonacci sequence and golden number\n", "\n", "## Try me\n", "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/ffraile/computer_science_tutorials/blob/main/source/Extra%20Exercises/Ex1.%20Fibonacci%20(SOL).ipynb)[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/ffraile/computer_science_tutorials/main?labpath=source%2FExtra%20Exercises%2FEx1.%20Fibonacci%20(SOL).ipynb)\n", "\n", "The Fibonacci sequence is the following infinite sequence of natural numbers:\n", "`0 1 1 2 3 5 8 13 21 34 55 89 144 ...`\n", "\n", "The sequence begins with the numbers 0 and 1. From these, each term is the sum of the previous two.\n", "\n", "As a curiosity, it has numerous applications in computer science, mathematics, and game theory. It also appears in biological settings, such as branching in trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke and in how DNA encodes the growth of complex organic forms. Similarly, it is found in the spiral structure of the shell of some molluscs.\n", "\n", "In addition, from the Fibonacci sequence, the **golden number** can be obtained, also with properties and uses in art and architecture. The value of the golden number is `1.618033988749894848204586834365...`. An approximation to this value can be calculated by dividing a number in the Fibonacci sequence by the immediately preceding one. The further these values are taken in the Fibonacci sequence, the closer the value of the division will be to the golden number. For example,\n", "\n", "`21/13 = 1.61538461...\n", "89/55 = 1.618181... `\n", "\n", "In Python, the elements of an array can be accessed through the index in square brackets, starting with 0, `array[0]`.\n", "\n", "The last elements of the array can be accessed directly using negative indices, for example, `array[-1]` would be the last element of the array, `array [-2]` the second to last, and so on.\n", "\n", "In Python, you can iterate through the elements of an array using the `for` loop. We can create a list of the indices through which we are going to iterate (from 0 to the last available element in the array) with the `range()` function. For example, if an array has 5 elements,\n", "\n", "`fibo = [0, 1, 1, 2, 3]\n", "for index in range(5):\n", " print (fibo[index]) `\n", " \n", "The above code iterates through the elements of the array and prints each one of them. The *index* values range from 0 to 4, a different value each iteration.\n", "\n", "With the `append()` function, an element is added to the end of the array. So for example we would add the value 5 to the end of the array:\n", "\n", "`fibo.append(5)`\n", "\n", "With everything explained so far, **develop the following program**:\n", "\n", "A program that from an array with the values `[0, 1]` generates a Fibonacci sequence and stores it in an array. The number of elements in the new array is up to the programmer's choice, but it will be at least 25 elements. Print the Fibonacci array per screen.\n", "\n", "Calculate from the last two elements of the Fibonacci series, an approximation to the golden number and print it on the screen. If we increase the length of the array by calculating more values of the Fibonacci series, does it improve the precision of the calculation of the golden number? Calculate it again with a larger number of elements and answer the question.\n" ] }, { "cell_type": "markdown", "source": [ "The following flow chart diagram illustrates the algorithm used to generate the Fibonacci series:\n", "\n", "![Fibonacci sequence](img/fibonacci.png)" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393]\n" ] } ], "source": [ "iters = 25\n", "\n", "fib = [0, 1]\n", "for index in range(iters):\n", " next_num = fib[-1] + fib[-2]\n", " fib.append(next_num)\n", "\n", "\n", "print(fib)" ] }, { "cell_type": "markdown", "source": [ "Now, let us calculate the golden number from the last two elements of the Fibonacci series:" ], "metadata": { "collapsed": false } }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1.6180339886704431\n" ] } ], "source": [ "golden = fib[-1]/fib[-2]\n", "print(golden)" ] }, { "cell_type": "markdown", "source": [ "## Analysis questions\n", "These questions are designed to help you better understand the code above. Try to answer them by yourself before asking for help.\n", "\n", "1. **Loop Mechanics**: What is the purpose of the `for` loop? How many times will it iterate? How would you modify the code to stop when the sequence has a given length?\n", "\n", "2. **Array Methods**: What is the purpose of the `append()` function? What would happen if you used the `insert()` function instead?\n", "\n", "3. **Indexing**: How is indexing used to calculate the next number in the sequence? How is it used to calculate the golden number?\n", "\n", "4. **Variable Types**: What is the type of the variable `fib`? What is the type of the variable `index`? And the variable `golden`? Would the program work if you changed the type of any of these variables?\n", "\n" ], "metadata": { "collapsed": false } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 4 }